package offer_test_40;

//：统计一个数字在排序数组中出现的次数。例如输入排序数组{1,2,3,3,3，3,3,4,5}
//和数字3，由于3在这个数组中出现了4次，因此输出4。
public class eighteen_GetNumberOfK {
	public static void main(String[] args) {
		int[] array={1,2,3,3,3,3,3,4,5};
		getNumOfK(array, 3);
	}

	public static void getNumOfK(int[] array, int number) {
		int begin=binarySearchFirstK(array, 0, array.length-1, number);
		System.out.println(begin);
		int end=binarySearchLastK(array, 0, array.length-1, number);
		System.out.println(end);
		System.out.println(end-begin+1);
	}

	public static int binarySearchFirstK(int[] array, int begin, int end, int number) {
		int mid = (begin + end) / 2;
		if (number < array[begin] || number > array[end] || begin > end) {
			return -1;
		}
		if (number < array[mid]) {
			return binarySearchFirstK(array, begin, mid - 1, number);
		} else if (number > array[mid]) {
			return binarySearchFirstK(array, mid + 1, end, number);
		} else {
			if((number!=array[mid-1]&&mid-1>=0)||mid==0){
				return mid;
			}else{				
				return binarySearchFirstK(array, begin, mid-1, number);
			}
		}
	}
	
	public static int binarySearchLastK(int[] array, int begin, int end, int number) {
		int mid = (begin + end) / 2;
		if (number < array[begin] || number > array[end] || begin > end) {
			return -1;
		}
		if (number < array[mid]) {
			return binarySearchLastK(array, begin, mid - 1, number);
		} else if (number > array[mid]) {
			return binarySearchLastK(array, mid + 1, end, number);
		} else {
			if((number!=array[mid+1]&&mid+1<=end)||mid==end){
				return mid;
			}else{				
				return binarySearchLastK(array, mid + 1, end, number);
			}
		}
	}
}
